package pers.qianyu.month_202012.date_20201207.sliding_window;

import org.junit.*;

import java.util.*;

/**
 * 76. 最小覆盖子串
 * https://leetcode-cn.com/problems/minimum-window-substring/
 *
 * @author mizzle rain
 * @date 2020-12-07 15:25
 */
public class MinWindow {
    public String minWindow(String s, String t) {
        int left = 0, right = 0, valid = 0;
        int start = 0, end = Integer.MAX_VALUE;
        HashMap<Character, Integer> need = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            int count = need.getOrDefault(t.charAt(i), 0);
            need.put(t.charAt(i), count + 1);
        }
        HashMap<Character, Integer> window = new HashMap<>();
        while (right < s.length()) {
            char c1 = s.charAt(right);
            int count = need.getOrDefault(c1, 0);
            if (count > 0) {
                window.put(c1, window.getOrDefault(c1, 0) + 1);
                if (window.get(c1).equals(need.get(c1))) {
                    valid++;
                }
            }
            right++;
            while (valid == need.size()) {
                if (right - left < end - start) {
                    start = left;
                    end = right;
                }
                char c2 = s.charAt(left);
                if (need.containsKey(c2)) {
                    if (window.get(c2).equals(need.get(c2))) {
                        valid--;
                    }
                    window.put(c2, window.getOrDefault(c2, 0) - 1);
                }
                left++;
            }
        }
        return end - start == Integer.MAX_VALUE ? "" : s.substring(start, end);
    }

    @Test
    public void test1() {
        String s = "ADOBECODEBANC";
        String t = "ABC";
        String result = new MinWindow().minWindow(s, t);
        System.out.println("result = " + result);
    }
}
